package com.fanshuai.algorithms.datastructure.priorityqueue;

import java.util.HashMap;

/**
 * hash链表，hash表和链表的结合。有如下特性：
 * 插入、删除、 查找复杂度为o(1)
 * 链表按照访问时间排序
 * 当超过LRU容量时，删除最久未访问的数据
 * @param <K>
 * @param <V>
 */
public class HashLinkedListLRUCache<K, V> implements LRUCache<K, V> {
    private static class Node<K, V> {
        public K key;
        public V value;
        public Node<K, V> pre;
        public Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private static class DoubleList<K, V> {
        private Node<K, V> head;
        private Node<K, V> tail;
        private int size;

        public DoubleList() {
            Node<K, V> node = new Node<K, V>(null, null);
            head = node;
            tail = node;
            size = 0;
        }

        public void addFirst(Node<K, V> node) {
            node.next = head.next;
            if (head.next != null) {
                head.next.pre = node;
            }
            head.next = node;
            node.pre = head;

            if (size == 0) {
                tail = node;
            }
            size++;
        }

        public void removeNode(Node<K, V> node) {
            Node<K, V> next = node.next;
            node.pre.next = next;
            if (next != null) {
                next.pre = node.pre;
            }

            if (node == tail) {
                tail = node.pre;
            }

            node.next = null;
            node.pre = null;
            node = null;
            size--;
        }

        public K removeLast() {
            K key = tail.key;

            Node<K, V> pre = tail.pre;
            pre.next = null;
            tail.pre = null;
            tail = null;

            tail = pre;
            size--;

            return key;
        }

        public int size() {
            return size;
        }
    }

    private DoubleList<K, V> doubleList;
    private HashMap<K, Node<K, V>> map;
    private int capacity;

    public HashLinkedListLRUCache(int capacity) {
        this.capacity = capacity;
        doubleList = new DoubleList<>();
        map = new HashMap<>();
    }

    @Override
    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (null == node) {
            return null;
        }

        doubleList.removeNode(node);
        doubleList.addFirst(node);
        return node.value;
    }

    @Override
    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            node.value = value;
            doubleList.removeNode(node);
            doubleList.addFirst(node);
        } else {
            if (map.size() == capacity) {
                K lastKey = doubleList.removeLast();
                map.remove(lastKey);
            }

            node = new Node<>(key, value);
            doubleList.addFirst(node);
            map.put(key, node);
        }
    }

    @Override
    public void delete(K key) {
        Node<K, V> node = map.get(key);
        if (null != node) {
            map.remove(key);
            doubleList.removeNode(node);
        }
    }

    public static void main(String[] args) {
        DoubleList<String, Integer> list = new DoubleList<>();
        list.addFirst(new Node<>("1", 1));
        list.addFirst(new Node<>("2", 2));
        list.addFirst(new Node<>("3", 3));

        System.out.println(list.size());
        while (list.size() > 0) {
            System.out.println("last key=" + list.removeLast());
        }

        LRUCache<String, Integer> cache = new HashLinkedListLRUCache<>(10);
        for (int i = 0; i < 50; i++) {
            cache.put(String.valueOf(i), i);
        }

        for (int i = 0; i < 50; i++) {
            System.out.println("key=" + i + ", value=" + cache.get(String.valueOf(i)));
        }
    }
}
